package solutions.leetcode.normal;

import solutions.lib.BaseSolution;
import solutions.lib.ListNode;
import solutions.lib.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/">109. 有序链表转换二叉搜索树</a>
 */
public class Solution109 extends BaseSolution {

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        int mid = list.size() / 2;
        TreeNode rst = new TreeNode(list.get(mid).val);
        build(rst, list, 0, mid - 1, true);
        build(rst, list, mid + 1, list.size() - 1, false);
        return rst;
    }

    private void build(TreeNode parent, List<ListNode> list, int left, int right, boolean isLeft) {
        if (left > right) {
            return;
        }
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(list.get(mid).val);
        if (isLeft) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        build(node, list, left, mid - 1, true);
        build(node, list, mid + 1, right, false);
    }

    public static void main(String[] args) {
        Solution109 solution = new Solution109();
    }
}